class Solution {
    int row, col;
    int ret = 0;

    void dfs(vector<vector<int>>& grid, int m, int n)
    {
        if (m < 0 || n < 0 || m >= row || n >= col || grid[m][n] != 1)
            return;

        ret += 4;
        if (m > 0 && grid[m - 1][n] == 2) ret -= 2;          //上面已经有陆地
        if (m < row - 1 && grid[m + 1][n] == 2)   ret -= 2;  //下面已经有陆地
        if (n > 0 && grid[m][n - 1] == 2) ret -= 2;          //左边已经有陆地
        if (n < col - 1 && grid[m][n + 1] == 2)   ret -= 2;  //右边已经有陆地

        grid[m][n] = 2;
        dfs(grid, m - 1, n);    //上
        dfs(grid, m, n - 1);    //左
        dfs(grid, m + 1, n);    //下
        dfs(grid, m, n + 1);    //右
    }
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        row = grid.size();
        col = grid[0].size();

        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (grid[i][j] == 1)
                {
                    dfs(grid, i, j);
                    break;
                }

        return ret;

    }
};